# -*- encoding: utf-8 -*-
'''
Filename         :4_findMedianSortedArrays.py
Description      :
Time             :2022/08/03 09:08:41
Author           :daiyizheng
Email            :387942239@qq.com
Version          :1.0
'''
from typing import List


class Solution:
    # 解法一暴力求解
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums = sorted(nums1+nums2)
        length = len(nums)
        if length == 0:
            return 0
        if length%2==0:
            return (nums[length//2-1] + nums[length//2])/2
        else:
            return float(nums[length//2])
        

    # 找K大的数据
    def getKmin(self, begin1, end1, begin2, end2, k):
        len1 = end1 - begin1 + 1
        len2 = end2 - begin2 + 1
        if len1 == 0:
            return self._nums2[begin2+k-1]
        if len2 == 0:
            return self._nums1[begin1+k-1]
        if k == 1:
            return min(self._nums1[begin1],self._nums2[begin2])
        i = begin1 + min(k // 2,len1) - 1
        j = begin2 + min(k // 2,len2) - 1
        if self._nums1[i] > self._nums2[j]:
            return self.getKmin(begin1,end1,j+1,end2,k-(j-begin2+1))
        else:
            return self.getKmin(i+1,end1,begin2,end2,k-(i-begin1+1))

    def findMedianSortedArrays1(self, nums1:List, nums2:List):
        self._nums1 = nums1
        self._nums2 = nums2
        self._m = len(nums1)
        self._n = len(nums2)
        if self._m == 0 and self._n == 0:
            raise ("nums1 and nums2 size is 0")
        left = (self._m + self._n + 1) // 2
        right = (self._m + self._n + 2) // 2
        return (self.getKmin(0,self._m-1,0,self._n-1,left)+self.getKmin(0,self._m-1,0,self._n-1,right)) / 2

    ## 二分查找
    def findMedianSortedArrays2(self, nums1:List, nums2:List): 
        m = len(nums1)
        n = len(nums2)
        if m>n:
            return self.findMedianSortedArrays2(nums1 = nums2, nums2 = nums1)
        ## 规定i在分割线右边，所以i可以取m
        i_min = 0
        i_max = m
        while i_min <= i_max:
            i = (i_min+i_max) // 2
            j = (m+n+1) // 2 - i
            if i != 0 and j != n and nums1[i-1] > nums2[j]:
                i_max = i - 1
            elif j != 0 and i != m and nums2[j-1] > nums1[i]:
                i_min = i + 1
            else:
                if i == 0:
                    max_left = nums2[j-1]
                elif j == 0:
                    max_left = nums1[i-1]
                else:
                    max_left = max(nums1[i-1],nums2[j-1])
                if (m+n) % 2 == 1:
                    return max_left
                if i == m:
                    max_right = nums2[j]
                elif j == n:
                    max_right = nums1[i]
                else:
                    max_right = min(nums1[i],nums2[j])
                return (max_left+max_right) / 2
        



if __name__ == '__main__':
    a = Solution().findMedianSortedArrays2([1,3,5,7], [2,4,6,8,9])